import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] pushed = new int[]{1,2,3,4,5};
        int[] popped = new int[]{5,1,2,3,4};
        System.out.println(s.validateStackSequences(pushed, popped));
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        /**
         * 验证栈序列
         * 解题思路：
         *  使用栈进行模拟，按照入栈顺序进行入栈，并持续根据出栈顺序判断是否能够出栈
         *  若是出栈元素遍历完成，则表示序列正确*/
        // 1 预处理
        int n = pushed.length;
        Stack<Integer> stack = new Stack<>();
        int popIndex = 0;
        int pushIndex = 0;

        // 2 循环枚举并使用栈模拟
        while(pushIndex < n && popIndex < n) {
            // -栈为空入栈，或者栈顶元素与当前出栈元素不一致入栈
            while(pushIndex < n && (stack.isEmpty() || stack.peek() != popped[popIndex])) {
                stack.push(pushed[pushIndex++]);
            }
            // -出栈（可能也会连续出，故使用while循环，这样可以避免在循环外继续处理剩余元素）
            while(!stack.isEmpty() && stack.peek() == popped[popIndex]) {
                stack.pop();
                popIndex++;
            }
        }

        // 3 返回值
        return popIndex == n;
    }

    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };

    public List<List<Integer>> levelOrder(Node root) {
        /**
         * N叉树的遍历
         * 遍历当前一层时，将下一层的元素入队
         * 代码一次过，使用的基本就是bfs查找路径长度算法的思想，步骤为：初始化 => 出本层节点并收集本层节点的子节点 => 循环上一步
         * 总的思路就是一层一层向下全面扩散*/
        // 1 预处理
        List<List<Integer>> retArray = new LinkedList<>();
        // -创建队列并使用根节点初始化
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        // 2 层序遍历
        while(!queue.isEmpty()) {
            // -1 记录本层节点个数，创建tempArray收集本层节点值
            int n = queue.size();
            List<Integer> tempArray = new LinkedList<>();

            // -2 出一层节点，并入队下一层节点
            for(int i = 0; i < n; i++) {
                // -3 出队节点
                Node curNode = queue.poll();
                // -跳过空值
                if(curNode == null) {
                    continue;
                }
                // -记录节点值
                tempArray.add(curNode.val);
                // -入队下层节点
                for(Node e: curNode.children) {
                    queue.offer(e);
                }
            }

            // -4 整合本层元素（若是本层均为null，则数组为空）
            if(!tempArray.isEmpty()) {
                retArray.add(tempArray);
            }
        }

        // 3 返回值
        return retArray;
    }
}
